#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int maxProfit(vector<int> &prices) {
    vector<int> left(prices.size(), 0);
    vector<int> right(prices.size(), 0);
    int profit = 0;

    if (prices.size() <= 1) return profit;
    if (prices.size() == 2) {
	if (prices[0] <= prices[1]) return prices[1] - prices[0];
	else return 0;
    }

    int curMin = prices[0];
    int curBenefit = 0;
    for (int i = 1; i < prices.size(); i++) {
	if (prices[i] - curMin > curBenefit) 
	    curBenefit = prices[i] - curMin;
	
	left[i] = curBenefit;
        if (curMin > prices[i]) 
	    curMin = prices[i];
    }

    int curMax = prices[prices.size()-1];
    curBenefit = 0;
    for (int i = prices.size()-2; i > 0; i--) {
	if (curMax - prices[i] > curBenefit) 
	    curBenefit = curMax - prices[i];

	right[i] = curBenefit;
	if (curMax < prices[i])
	    curMax = prices[i];
    }

   for (int i = 1; i < prices.size() -1; i++) {
        if (left[i] + right[i] > profit) 
	    profit = left[i] + right[i];
   }
    return profit;
}

//add better code
   int maxProfit3(vector<int> &prices) {
        if (prices.size() < 2) return 0;
        int maxProfit = 0;
        int curMin = prices[0];
        vector<int> dp1(prices.size(), 0), dp2(prices.size(), 0); 

        for (int i = 1; i < prices.size(); i++) {
            maxProfit = max(maxProfit, prices[i] - curMin);
            dp1[i] = maxProfit;
            curMin = min(curMin, prices[i]);
        }   

        maxProfit = 0;
        int curMax = prices[prices.size()-1];
        for (int i = prices.size()-2; i >= 0; i--) {
            maxProfit = max(maxProfit, curMax - prices[i]);
            dp2[i] = maxProfit;
            curMax = max(curMax, prices[i]);
        }   
        maxProfit = 0;
        for (int i = 0; i < prices.size(); i++)
            maxProfit = max(maxProfit, dp1[i] + dp2[i]);

        return maxProfit;
    
    }   


//test on 1337 and pass all the test
int main(int argc, char **argv)
{

}
